package airthmetic.exercise.divideconquer;

public class _169_多数元素 {
    public static int majorityElement(int[] nums) {
        return divideConquer(nums,0, nums.length-1);
    }

    public static int divideConquer(int[] nums, int start, int end){
        if(start == end){
            return nums[start];
        }
//         int mid = (end - start) >> 1;
        int  mid = (end-start)/2 + start;
        int leftMajor = divideConquer(nums,start,mid);
        int rightMajor = divideConquer(nums, mid + 1, end);

        if(leftMajor == rightMajor){
            return leftMajor;
        }
        return count(leftMajor, nums,start,end) > count(rightMajor,nums,start,end) ? leftMajor: rightMajor;
    }

    public static int count(int num, int[] nums, int start, int end){
        int count = 0;
        for(int i= start; i<= end; i++){
            if(nums[i] == num){
                count++;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{8,9,8,9,8};
        int[] nums2 = new int[]{3,2,3};
        int[] nums3 = new int[]{2,2,1,1,1,2,2};
        System.out.println(majorityElement(nums));

//        System.out.println(majorityElement(nums2));
        System.out.println(majorityElement(nums3));
    }
}
